package 中等.搜索.深度优先搜索;

/**
 * 在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，
 * 其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0
 * 返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找
 * 到加号标志，则返回 0 。
 * 一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，
 * 以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。
 * 注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/largest-plus-sign
 */
public class 最大加号标志_764 {

    public static void main(String[] args) {

        // 101
        // 111
        // 111
        System.out.println(orderOfLargestPlusSign(3, new int[][]{{0, 1}}));

    }

    public static int orderOfLargestPlusSign(int n, int[][] mines) {
        int ans = 0;
        int[][] grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                grid[i][j] = 1;
            }
        }
        for (int[] mine : mines) {
            grid[mine[0]][mine[1]] = 0;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int minLen = 500;
                int row = i, column = j;

                int curLen = 0;
                while (row >= 0 && grid[row][column] == 1) {
                    row--;
                    curLen++;
                }
                minLen = Math.min(minLen, curLen);

                row = i;
                curLen = 0;
                while (row < n && grid[row][column] == 1 && curLen < minLen) {
                    row++;
                    curLen++;
                }
                minLen = Math.min(minLen, curLen);

                row = i;
                curLen = 0;
                while (column >= 0 && grid[row][column] == 1 && curLen < minLen) {
                    column--;
                    curLen++;
                }
                minLen = Math.min(minLen, curLen);

                column = j;
                curLen = 0;
                while (column < n && grid[row][column] == 1 && curLen < minLen) {
                    column++;
                    curLen++;
                }
                minLen = Math.min(minLen, curLen);

                ans = Math.max(ans, minLen);
            }
        }

        return ans;
    }

    // TODO 预处理+前缀和

}
